package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_10_Training {
    //求出最长好子序列 I
    int[][][] memo;

    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        memo = new int[n][n + 1][k + 1];
        for (int[][] row : memo) {
            for (int[] a : row) {
                Arrays.fill(a, -1);
            }
        }
        return dfs(nums, 0, n, k);
    }

    int dfs(int[] nums, int i, int j, int k) {
        if (i == nums.length) {
            return 0;
        }
        if (memo[i][j][k] != -1) {
            return memo[i][j][k];
        }

        // 选择当前元素 (1.选第一个,2.k>0,3.num[i]=nums[j])
        int branch1 = 0;
        if (j == nums.length || k > 0 || nums[i] == nums[j]) {
            branch1 = dfs(nums, i + 1, i, (j == nums.length || nums[i] == nums[j]) ? k : k - 1) + 1;
        }

        // 不选择当前元素
        int branch2 = dfs(nums, i + 1, j, k);

        memo[i][j][k] = Math.max(branch1, branch2);
        return memo[i][j][k];
    }
}
